/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
    public:
        bool isPalindrome(ListNode* head) {

            if (!head || !head->next)
                return true;

            ListNode *pfast = head;
            ListNode *pslow = NULL;

            while(pfast && pfast->next) {
                pfast = pfast->next->next;
                if (!pslow) {
                    pslow = head;
                } else {
                    pslow = pslow->next;
                }
            }

            ListNode *pleft = head;
            ListNode *pright = NULL;
            if (pfast) {
                // odd
                pright = pslow->next->next;
                pslow->next = NULL;

            } else {
                // even
                pright = pslow->next;
                pslow->next = NULL;
            }
            pright = reverse(pright);

            while(pleft && pright && pleft->val == pright->val) {
                pleft = pleft -> next;
                pright = pright -> next;
            }

            if (!pright) {
                return true;
            }
            return false;
        }

        ListNode* reverse(ListNode* head) {

            if (!head || !head->next)
                return head;

            ListNode *prev = NULL;
            ListNode *p = head, *q = NULL;

            while(p) {
                q = p->next;
                p->next = prev;
                prev = p;
                p = q;
            }
            return prev;

        }

};




